package com.study.lu;

import java.util.HashMap;
import java.util.Map;

public class 斐波那契数列 {
    /**
     * 斐波那契数列：
     * 每一位数的值等于前两位之和。前两位固定为0和1
     *
     * @param args
     */
    public static void main(String[] args) {
        // 0，1，2，3，5，8
        System.out.println(bf(10L));

        System.out.println(quChongbf(10L));

        System.out.println(twoPiont(10L));

    }

    /**
     * 在斐波那契数列中 一个数等于 前两个数相加，那么从前往后推，只要记住最前面两个数，那么就能得到下个数的值
     *
     * @param index
     * @return
     */
    private static int twoPiont(Long index) {
        int min = 0, max = 1;
        int sum = 0;
        for (int i = 2; i <= index; i++) {
            sum = max + min;
            min = max;
            max = sum;
        }

        return sum;
    }

    /**
     * 递归中存在重复计算的过程，所以需要把计算过的存储起来，这样可以减少重复计算
     *
     * @param index
     * @return
     */
    private static Long quChongbf(long index) {
        Map<Long, Long> map = new HashMap<>(16);
        return doQuChongbf(map, index);
    }

    private static Long doQuChongbf(Map<Long, Long> map, long index) {
        if (null != map.get(index)) {
            return map.get(index);
        }
        if (index == 0 || index == 1) {
            map.put(index, index);
            return index;
        } else {
            Long res = doQuChongbf(map, index - 1);
            map.put(index - 1, res);
            Long res2 = doQuChongbf(map, index - 2);
            return res + res2;
        }
    }

    private static Long bf(Long index) {
        return doBf(index);
    }

    private static Long doBf(Long index) {
        if (index == 0 || index == 1) {
            return index;
        } else {
            return doBf(index - 1) + doBf(index - 2);
        }
    }
}
